package _11_整理题目._1_链表指针._合并链表;

import org.junit.Test;
import util.ListNode;


/**
 *
 *
 * 将两个有序的链表合并为一个新链表，
 * 要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。
 * 
 * 建立一个 fake 节点，使用一个 tail 指针，每次连接较小的节点
 */
public class _03_合并两个有序链表 {
    
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        ListNode fake = new ListNode(0);
        ListNode point = fake;
        while (l1!=null && l2!=null) {
            if (l1.val <= l2.val) {
                point.next = l1;
                l1 = l1.next;
            } else {
                point.next = l2;
                l2 = l2.next;
            }
            point = point.next;
        }
        point.next = (l1==null) ? l2 : l1;
        return fake.next;
    }
    
    @Test
    public void main() {
        Integer[] array1 = {1, 3, 7, 9, 22};
        Integer[] array2 = {1, 2, 8, 10, 44, 55, 77};
        ListNode head1 = ListNode.getListFromArray(array1);
        ListNode head2 = ListNode.getListFromArray(array2);
        ListNode.printList(head1);
        ListNode.printList(head2);
        ListNode result = mergeTwoLists(head1, head2);
        ListNode.printList(result);
    }
    
}
